package com.sparsearr.datastructures.ztr.hashtable;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import java.util.Scanner;

/**
 * @Author: ZhaoTR
 * @Date: Created in 2025/6/3 21:03
 * @Description: 谷歌面试上机：哈希表
 * @Version: 1.0
 */

public class HashTableDemo {
    private static final Logger logger = LogManager.getLogger(HashTableDemo.class);

    public static void main(String[] args) {
        HashTable hashTable = new HashTable(7);

        String key;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("==========员工管理系统==========");
            System.out.println("add: 添加员工");
            System.out.println("list: 显示员工");
            System.out.println("find: 查找员工");
            System.out.println("delete: 删除员工");
            System.out.println("exit: 退出程序");

            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("请输入员工id");
                    int id = scanner.nextInt();
                    System.out.println("请输入员工姓名");
                    String name = scanner.next();
                    Employee employee = new Employee(id, name);
                    hashTable.add(employee);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.println("请输入员工id");
                    id = scanner.nextInt();
                    hashTable.findEmployeeById(id);
                    break;
                case "delete":
                    System.out.println("请输入要删除的员工id");
                    id = scanner.nextInt();
                    hashTable.deleteEmployeeById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    System.out.println("无效的选择，请重新输入！");
                    break;
            }
        }
    }

}

// 员工类
class Employee {
    public int id;
    public String name;
    public Employee next;

    public Employee(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

// 创建哈希表
class HashTable {
    // 创建一个数组，数组的长度是链表个数
    private final EmployeeLinkedList[] employeeLinkedListArray;

    // 表示多少条链表
    private final int size;

    // 构造器
    public HashTable(int size) {
        this.size = size;
        // 初始化数组
        employeeLinkedListArray = new EmployeeLinkedList[size];
        // 创建链表，每个链表是一个链表对象 分别初始化链表
        for (int i = 0; i < size; i++) {
            employeeLinkedListArray[i] = new EmployeeLinkedList();
        }
    }

    // 添加员工
    public void add(Employee employee) {
        // 确定添加员工的位置
        int e = hashFun(employee.id);
        // 将员工添加到对应的链表中
        employeeLinkedListArray[e].add(employee);
    }

    // 遍历哈希表
    public void list() {
        for (int i = 0; i < size; i++) {
            employeeLinkedListArray[i].list(i);
        }
    }

    // 根据id查询员工
    public void findEmployeeById(int id) {
        int e = hashFun(id);
        Employee employee = employeeLinkedListArray[e].findEmployeeById(id);
        if (employee != null) {
            System.out.println("在第" + (e + 1) + "链表，找到该员工" + employee);
        } else {
            System.out.println("没有找到该员工");
        }
    }

    // 删除员工
    public void deleteEmployeeById(int id) {
        int e = hashFun(id);
        boolean deleted = employeeLinkedListArray[e].deleteEmployeeById(id);
        if (deleted) {
            System.out.println("成功删除ID为 " + id + " 的员工");
        } else {
            System.out.println("未找到ID为 " + id + " 的员工");
        }
    }

    // 散列函数，使用取模法
    public int hashFun(int id) {
        return id % size;
    }

}


// 创建一个雇员的链表
class EmployeeLinkedList {
    // 头指针，执行第一个节点，在链表为空时为null
    private Employee head;

    //  添加员工
    // 添加雇员到链表
    // 1. 添加雇员时，需要考虑是否为第一个节点 id 是自增长的，即id是唯一从小到大
    // 2. 将员工直接添加到链表当中的最后
    public void add(Employee employee) {
        // 判断链表是否为空
        if (head == null) {
            head = employee;
            return;
        }
        // 如果不是第一个，则使用一个辅助的指针，帮助定位到最后
        Employee curEmp = head;
        while (true) {
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
        // 退出while循环时，curEmp指向链表的最后
        curEmp.next = employee;
    }

    // 遍历链表
    public void list(int no) {
        // 判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        System.out.print("第" + (no + 1) + "链表信息为：");
        Employee curEmp = head;
        while (true) {
            System.out.printf("=> id => %d name=%s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) {
                break;
            }
            // 将curEmp后移
            curEmp = curEmp.next;
        }
        System.out.println();
    }

    // 根据id查找雇员
    // 找到就返回，找不到返回null
    public Employee findEmployeeById(int id) {
        // 判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        // 辅助指针
        Employee curEmp = head;

        while (true) {
            if (curEmp.id == id) {
                // 找到
                break;
            }
            if (curEmp.next == null) {
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }

    // 根据id删除雇员
    public boolean deleteEmployeeById(int id) {
        if (head == null) {
            System.out.println("链表为空，无法删除");
            return false;
        }

        // 如果是头节点
        if (head.id == id) {
            head = head.next;
            return true;
        }

        Employee prev = head;
        Employee cur = head.next;

        while (cur != null) {
            if (cur.id == id) {
                // 删除当前节点
                prev.next = cur.next;
                return true;
            }
            prev = cur;
            cur = cur.next;
        }
        // 没有找到
        return false;
    }
}